package graphquerying.reachability;

import java.util.ArrayList;
import java.util.HashMap;

import model.Graph;
import model.Node;

/**
 * A directed acylic graph class represented by adjoined linked-list
 * Only be used for reachability querying
 * @author BaiJian
 */
public class RGraph {
	
	/**
	 * The identifier of RGraph(Readonly)
	 */
	private String id;
	
	/**
	 * Nodes mapping from id to instance(Readonly)
	 */
	private HashMap<String, RNode> nodesMap;
	
	/**
	 * Id list of R-Nodes(Readonly)
	 */
	private ArrayList<String> nodesIdList;
	
	/**
	 * Id list of 0-in degree nodes(Readonly)
	 */
	private ArrayList<String> rootsIdList;
	
	/**
	 * Mapped from node's id to R-node's id
	 * Identify which R-node the node belongs to
	 */
	private HashMap<String, String> idMap;
	
	/**
	 * The cache of R-Graph
	 */
	private static HashMap<String, RGraph> rGraphMap = new HashMap<String, RGraph>();
	
	/**
	 * Used for DFS labeling
	 */
	private int timeStamp;
	
	/**
	 * Amount of edges per DFS flow
	 */
	private final int EDGES_PER_ROUND = 50000;
	
	public RGraph(Graph graph) {
		System.out.println("Convert to directed acylic graph, please wait...");
		long startTime = System.currentTimeMillis();
		id = String.valueOf(graph.hashCode());
		nodesMap = new HashMap<String, RNode>();
		nodesIdList = new ArrayList<String>();
		rootsIdList = new ArrayList<String>();
		idMap = new HashMap<String, String>();
		for (Node node : graph.nodes) {
			idMap.put(node.id, node.id);
			nodesIdList.add(node.id);
			nodesMap.put(node.id, new RNode(node.id));
			
		}

		for (int i = 0; i < graph.edges.size(); i += EDGES_PER_ROUND) {
			convertToDirectedAcylicGraph(graph, i, i + EDGES_PER_ROUND - 1);
			//Refresh idMap after one DAG convertation
			for (Node node : graph.nodes) {
				String parentRoot = idMap.get(node.id);
				idMap.put(node.id, idMap.get(parentRoot));
			}
		}
		
		//Find all root nodes and the amount of bridges
		int bridgeCount = 0;
		for (String rNodeId : nodesIdList) {
			if (nodesMap.get(rNodeId).getInDegree() == 0) {
				rootsIdList.add(rNodeId);
			}
			bridgeCount += nodesMap.get(rNodeId).getInDegree();
		}
		System.out.println("Done. Time cost: " + (System.currentTimeMillis() - startTime) + "ms");
		System.out.println(nodesIdList.size() + " strong component(s), " + bridgeCount + " edge(s) in total");
		rGraphMap.put(id, this);
	}
	
	/**
	 * Build a directed acylic R-graph
	 * 
	 * @param graph The source graph to be converted
	 */
	private void convertToDirectedAcylicGraph(Graph graph, int startEdgeIndex, int endEdgeIndex) {
		ArrayList<String> tempNodesList = new ArrayList<String>();
		HashMap<String, RNode> tempNodesMap = new HashMap<String, RNode>();
		HashMap<String, RNode> complementNodesMap = new HashMap<String, RNode>();
		
		//Copy the data of nodesIdList
		for (String nodeId : nodesIdList) {
			tempNodesMap.put(nodeId, new RNode(nodeId));
			complementNodesMap.put(nodeId, new RNode(nodeId));
			tempNodesList.add(nodeId);
		}
		
		//Copy the data of nodesMap
		for (String nodeId : nodesIdList) {
			for (String adjId : nodesMap.get(nodeId).getAdjRNodes()) {
				tempNodesMap.get(nodeId).getAdjRNodes().add(adjId);
				complementNodesMap.get(adjId).getAdjRNodes().add(nodeId);
			}
		}
		
		
		if (endEdgeIndex >= graph.edges.size()) {
			endEdgeIndex = graph.edges.size() - 1;
		}
		for (int i = startEdgeIndex; i <= endEdgeIndex; i++) {
			String sourceRoot = idMap.get(graph.edges.get(i).sourceNode.id);
			String targetRoot = idMap.get(graph.edges.get(i).targetNode.id);
			if (!sourceRoot.equals(targetRoot)) {
				RNode rNode = tempNodesMap.get(sourceRoot);
				if (!rNode.getAdjRNodes().contains(targetRoot)) {
					rNode.getAdjRNodes().add(targetRoot);
				}
				rNode = complementNodesMap.get(targetRoot);
				if (!rNode.getAdjRNodes().contains(sourceRoot)) {
					rNode.getAdjRNodes().add(sourceRoot);
				}
			}
		}
		nodesIdList.clear();
		nodesMap.clear();
		
		//Find the maximal connected components
		timeStamp = 0;
		for (String visitedId : tempNodesList) {
			if (tempNodesMap.get(visitedId).getStatus() == VisitedStatus.NOT_VISITED) {
				depthFirstSearch(tempNodesMap, visitedId, visitedId);
			}
		}
		quickSortFinishingTime(tempNodesList, tempNodesMap, 0, tempNodesList.size() - 1);
		timeStamp = 0;
		for (String visitedId : tempNodesList) {
			if (complementNodesMap.get(visitedId).getStatus() == VisitedStatus.NOT_VISITED) {
				depthFirstSearch(complementNodesMap, visitedId, visitedId);
				nodesIdList.add(visitedId); //Add the root id to the R-Graph's nodeslist
				nodesMap.put(visitedId, new RNode(visitedId));
			}
		}
		
		// Combine and generate DAG
		for (String visitedId : tempNodesList) {
			idMap.put(visitedId, complementNodesMap.get(visitedId).getRoot());
			RNode rNode = tempNodesMap.get(visitedId);
			String root = idMap.get(visitedId);
			RNode rootNode = nodesMap.get(root);
			for (String adjId : rNode.getAdjRNodes()) {
				String adjNodeRoot = complementNodesMap.get(adjId).getRoot();
				if (!adjNodeRoot.equals(root) && !rootNode.getAdjRNodes().contains(adjNodeRoot)) {
					rootNode.getAdjRNodes().add(adjNodeRoot);
					nodesMap.get(adjNodeRoot).setInDegree(nodesMap.get(adjNodeRoot).getInDegree() + 1);
				}
			}
		}
	}
	
	/**
	 * Native DFS algorithm
	 * @param nodesMap The nodes mapping of the R-graph
	 * @param currentId The current node's id
	 * @param root The id of the DFS-tree root node
	 */
	private void depthFirstSearch(HashMap<String, RNode> nodesMap, String currentId, String root) {
		RNode currentNode = nodesMap.get(currentId);
		currentNode.setStatus(VisitedStatus.BEING_VISITED);
		timeStamp++;
		currentNode.setDiscoverTime(timeStamp);
		for (String childId : currentNode.getAdjRNodes()) {
			if (nodesMap.get(childId).getStatus() == VisitedStatus.NOT_VISITED) {
				nodesMap.get(childId).setRoot(root);
				depthFirstSearch(nodesMap, childId, root);
			}
		}
		currentNode.setStatus(VisitedStatus.FINISHED);
		timeStamp++;
		currentNode.setFinishTime(timeStamp);
	}
	
	/**
	 * Quick sort the finishing time descendently
	 * @param tempNodesList The id list to be sorted
	 * @param tempNodesMap The id to R-Node instance mapping
	 * @param start The left bound
	 * @param end The right bound
	 */
	private void quickSortFinishingTime(ArrayList<String> tempNodesList, HashMap<String, RNode> tempNodesMap, int start, int end) {
		if (start < end) {
			int x = randomizedPartition(tempNodesList, tempNodesMap, start, end);
			quickSortFinishingTime(tempNodesList, tempNodesMap, start, x - 1);
			quickSortFinishingTime(tempNodesList, tempNodesMap, x + 1, end);
		}
	}
	
	/**
	 * The partition procedure of quick sort. Choose the pivot randomly
	 * @param tempNodesList The id list to be sorted
	 * @param tempNodesMap The id to R-Node instance mapping
	 * @param start The left bound
	 * @param end The right bound
	 * 
	 * @return The partition index
	 */
	private int randomizedPartition(ArrayList<String> tempNodesList, HashMap<String, RNode> tempNodesMap, int start, int end) {
		//Find the pivot randomly
		int r = (int)(Math.random() * (end - start + 1) + start);
		String tempKey = tempNodesList.get(r);
		tempNodesList.set(r, tempNodesList.get(end));
		tempNodesList.set(end, tempKey);
		String pivot = tempNodesList.get(end);
		int i = start - 1;
		for (int j = start; j < end; j++) {
			String keyJ = tempNodesList.get(j);
			if (tempNodesMap.get(keyJ).getFinishTime() >= tempNodesMap.get(pivot).getFinishTime()) {
				i++;
				tempKey = tempNodesList.get(i);
				tempNodesList.set(i, tempNodesList.get(j));
				tempNodesList.set(j, tempKey);
			}
		}
		i++;
		tempKey = tempNodesList.get(i);
		tempNodesList.set(i, tempNodesList.get(end));
		tempNodesList.set(end, tempKey);
		return i;
	}
	
	/**
	 * Initial nodes' visiting status before DFS running
	 */
	public void initialNodesVisitedStatus() {
		for (String id : nodesIdList) {
			nodesMap.get(id).setStatus(VisitedStatus.NOT_VISITED);
		}
	}

	public HashMap<String, RNode> getNodesMap() {
		return nodesMap;
	}

	public ArrayList<String> getNodesIdList() {
		return nodesIdList;
	}

	public String getId() {
		return id;
	}

	public ArrayList<String> getRootsIdList() {
		return rootsIdList;
	}

	public HashMap<String, String> getIdMap() {
		return idMap;
	}
	
	public static RGraph readCache(String rid) {
		return rGraphMap.get(rid);
	}
}
